Thực đơn
Sắp_xếp_nhanh Mã giả // left là chỉ số của phần tử đầu tiên của mảng // right là chỉ số của phần tử cuối cùng của mảng // số phần tử của mảng = right-left+1function partition(array, 'left', 'right', 'pivotIndex') 1.'pivotValue':= array['pivotIndex'] 2.swap array['pivotIndex'] and array['right'] // Move pivot to end 3.'storeIndex':= 'left' 4.for 'i' from 'left' to 'right'-1 // left ≤ i < right 1.if array['i'] < 'pivotValue' 1.swap array['i'] and array['storeIndex'] 2.'storeIndex':= 'storeIndex' + 1 5.swap array['storeIndex'] and array['right'] // Move pivot to its final place 6.return 'storeIndex'
function quicksort(array, 'left', 'right') // If the list has 2 or more items if 'left' < 'right' // See "Choice of pivot" section below for possible choices choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right' // Get lists of bigger and smaller items and final position of pivot 'pivotNewIndex':= partition(array, 'left', 'right', 'pivotIndex') // Recursively sort elements smaller than the pivot quicksort(array, 'left', 'pivotNewIndex' - 1) // Recursively sort elements at least as big as the pivot quicksort(array, 'pivotNewIndex' + 1, 'right')
#include<stdio.h>#include<conio.h>typedef int keytype;typedef struct{ keytype key;}recordtype;void Swap(recordtype *x, recordtype *y){ recordtype temp; temp = *x; *x = *y; *y = temp;}int FindPivot(recordtype a[],int i, int j){ keytype firstkey; int k; k=i+1; firstkey = a[i].key; while((k<=j)&&(a[k].key==firstkey)) k++; if(k>j) return -1; else if((a[k].key > firstkey)) return k; else return i;}int Partition(recordtype a[],int i, int j, keytype pivot){ int L, R; L=i; R=j; while(L<=R){ while (a[L].key < pivot) L++; while (a[R].key > pivot) R--; if (L < R) Swap(&a[L], &a[R]); } return L;}void QuickSort (recordtype a[], int i, int j){ keytype pivot; int pivotindex, k; pivotindex = FindPivot(a,i, j); if (pivotindex != -1){ pivot = a[pivotindex].key; k = Partition(a, i, j, pivot); QuickSort(a, i, k-1); QuickSort(a, k, j); }}int main(){ int n,i; recordtype a[50]; printf("nhap n: "); scanf("%d",&n); for(i=0;i<n;i++){ printf("nhap phan tu: "); scanf("%d",&a[i].key); } QuickSort(a, 0, n-1); for(i= 0;i<n;i++){ printf(" --- %d",a[i].key); } return 0;}
Nhiều người cho rằng việc khử đệ quy của sắp xếp nhanh thực ra không cần thiết, nó chỉ có tác dụng cho những người mới tiếp cận khoa học máy tính hiểu sâu sắc hơn về khái niệm đệ quy. Bản chất của các giải thuật đệ quy là lưu trữ các tham biến đệ quy vào một ngăn xếp (stack) để lần lượt lấy ra xử lý.
Khi khử đệ quy của giải thuật đệ quy, mỗi lần phân chia danh sách thành 2 danh sách con ta lưu trữ các tham số của danh sách đứng sau vào một ngăn xếp, rồi phân chia tiếp danh sách đứng trước.
Giải thuật đơn giản nhất để khử đệ quy của sắp xếp nhanh như sau:
Procedure QuickSort(a[1..n]) { Var list S, E; Int m:=1 S(m):=1; E(m):= n; While m>0 { k=S(m); l=E(m) m:=m-1; if l<k then { i=Part(k,l); m=m+1; S(m):=i+1 E(m):=l } } }
Ưu điểm của sắp xếp nhanh không đệ quy nằm ở những cải tiến của giải thuật trên đây. Có thể cải tiến theo những hướng sau: Cất vào ngăn xếp danh sách con ít phần tử hơn trong hai danh sách con và đối với các danh sách con có độ dài đủ nhỏ thì dùng một phương pháp sắp xếp sơ cấp (chẳng hạn sắp xếp chèn).
Một phương pháp chia khác là chia danh sách thành 3 danh sách con, lần lượt nhỏ hơn, bằng và lớn hơn phần tử chốt.
function quicksort(a) Var list less, equal, greater if length(a) ≤ 1 return a else select a pivot value pivot from a for each x in a if x < pivot then add x to less if x = pivot then add x to equal if x > pivot then add x to greater return concatenate(quicksort(less), equal, quicksort(greater))
Thực đơn
Sắp_xếp_nhanh Mã giảLiên quan
Sắp xếp nổi bọt Sắp xếp trộn Sắp xếp chèn Sắp xếp nhanh Sắp xếp chọn Sắp xếp vun đống Sắp xếp tô pô Sắp xếp đếm phân phối Sắp xếp theo cơ số Sắp xếpTài liệu tham khảo
WikiPedia: Sắp_xếp_nhanh